//
// Created by liushuai on 2021/1/15.
//

#include "uniquePaths.h"

using namespace std;
int uniquePaths(int m, int n) {
  int dp[m][n];
  for (int col = 0; col < n; col++) {
    for (int row = 0; row < m; row++) {
      if (col == 0 || row == 0)
        dp[row][col] = 1;
      else {
        dp[row][col] = dp[row - 1][col] + dp[row][col - 1];
      }
    }
  }
  return dp[m - 1][n - 1];
}
int uniquePathsArray(int m, int n, int *dp, int &col) {
  if (m == 1 || n == 1)
    dp[m * col + n] = 1;
  else {
    if (dp[m * col + n - 1] == 0)
      dp[m * col + n - 1] = uniquePathsArray(m, n - 1, dp, col);
    if (dp[col * (m - 1) + n] == 0)
      dp[(col) * (m - 1) + n] = uniquePathsArray(m - 1, n, dp, col);
    dp[m * (col) + n] = dp[m * (col) + n - 1] + dp[(col) * (m - 1) + n];
  }
  return dp[m * col + n];
}

int uniquePathsArray(int m, int n) {
  int row = m + 1;
  int col = n + 1;
  int *dp = new int[row * col]{};
  int res = uniquePathsArray(m, n, dp, col);
  delete[] dp;
  return res;
}

int uniquePaths1(int m, int n) {
  if (m == 1 || n == 1)
    return 1;
  else {
    int *dp = new int[(m + 1) * (n + 1)]{};
    for (int i = 1; i < m + 1; i++) {
      for (int j = 1; j < n + 1; j++) {
        if (i == 1 || j == 1)
          dp[i * (n + 1) + j] = 1;
        else
          dp[i * (n + 1) + j] =
              dp[i * (n + 1) + j - 1] + dp[(i - 1) * (n + 1) + j];
      }
    }
    int res = dp[(n + 1) * m + n];
    delete[] dp;
    return res;
  }
}
